Search for: All records

A $(β,δ,Δ)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $$Δ$$ such that for every vertex $$v\in V$$, the probability that $$\rm{ball}_G(v,γΔ)$$ is entirely contained in the cluster containing $$v$$ is at least $$e^{-βγ}$$ for every $$γ\in [0,δ]$$. Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter $$β$$, called the padding parameter, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with $$n$$ vertices, $$β= Θ(\log n)$$. Klein, Plotkin, and Rao showed that $$K_r$$-minor-free graphs have padding parameter $β= O(r^3)$, which is a significant improvement over general graphs when $$r$$ is a constant. A long-standing conjecture is to construct a padded decomposition for $$K_r$$-minor-free graphs with padding parameter $$β= O(\log r)$$. Despite decades of research, the best-known result is $β= O(r)$, even for graphs with treewidth at most $$r$$. In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth $$\rm{tw}$$ admit a padded decomposition with padding parameter $$O(\log \rm{tw})$$, which is tight. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: $$O(\sqrt{ \log n \cdot \log(\rm{tw})})$$ flow-cut gap, max flow-min multicut ratio of $$O(\log(\rm{tw}))$$, an $$O(\log(\rm{tw}))$$ approximation for the 0-extension problem, an $$\ell^{O(\log n)}_\infty$$ embedding with distortion $$O(\log \rm{tw})$$, and an $$O(\log \rm{tw})$$ bound for integrality gap for the uniform sparsest cut. 39 pages. This is the TheoretiCS journal version